/**
 * [381] O(1) 时间插入、删除和获取随机元素 - 允许重复
 *
 * @format
 * @lc app=leetcode.cn id=381 lang=javascript
 */

// @lc code=start
// dist:{"0":[0,1,4],"1":[2,3]}
// arr:[[0,0],[0,1],[1,0],[1,1],[0,2]]
var RandomizedCollection = function () {
    this.dist = {}
    this.arr = []
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function (val) {
    // 字典中是否存在该元素
    if (this.dist[val]) {
        // 在字典上记录元素在数组中的下标
        this.dist[val].push(this.arr.length)
        // 入栈新元素：[数值（键），字典对应（值）下标]
        this.arr.push([val, this.dist[val].length - 1])
        // 未新增不同元素
        return false
    } else {
        this.dist[val] = [this.arr.length]
        this.arr.push([val, 0])
        // 已新增不同元素
        return true
    }
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function (val) {
    // 字典中是否存在该元素
    if (this.dist[val]) {
        let len = this.dist[val].length
        // 获取待删除元素在数组中的下标
        const I = this.dist[val][len - 1]
        const END = this.arr[this.arr.length - 1]
        // 用末尾元素覆盖待删除元素
        this.arr[I] = END
        // 字典对应元素、数组末尾出栈
        this.arr.pop()
        this.dist[val].pop()
        // 更新字典
        // 清理字典中的空元素
        if (this.dist[val].length == 0) delete this.dist[val]
        // 删除元素和数组末尾不同值 or 删除元素和数组末尾同值但不是字典末尾元素
        if (val != END[0] || (this.dist[val] && val == END[0] && END[1] != len - 1)) this.dist[END[0]][END[1]] = I
        return true
    } else return false
}

/**
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function () {
    return this.arr[Math.floor(Math.random() * this.arr.length)][0]
}
// Accepted
// 32/32 cases passed (397 ms)
// Your runtime beats 71.43 % of javascript submissions
// Your memory usage beats 14.29 % of javascript submissions (100.6 MB)
/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
// debugger
// const functions = ["RandomizedCollection", "insert", "insert", "insert", "insert", "insert", "insert", "remove", "remove", "remove", "remove", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
// const values = [[], [1], [1], [2], [1], [2], [2], [1], [2], [2], [2], [], [], [], [], [], [], [], [], [], []]
// const obj = new RandomizedCollection()
// const results = [null]
// let result = null
// for (let i = 1; i < values.length; i++) {
//     console.log(functions[i], values[i][0])
//     result = obj[functions[i]](values[i][0])
//     results.push(result)
//     console.log(result, obj.dist, obj.arr)
// }
// console.log(results)
// @lc code=end
